package leetcode_动态规划._05最长递增子序列;

import java.util.Arrays;

/**
 * 最长递增子序列
 * 算法：
 *   dp[i] 表示到 i 为止的最长递增子序列
 *   两次循环
 *   如果 nums[i] > nums[j] & dp[i] <= dp[j] , ++dp[i]
 */
public class _300 {

    public int lengthOfLIS(int[] nums) {
        int ans = 0;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j] && dp[i] <= dp[j]) {
                    ++dp[i];
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans + 1;
    }
}
